package com.practice.tree;

import com.practice.util.BinaryTree;
import com.practice.util.BinaryTreeNode;

/**
 * Given a binary tree, find 2 leaf nodes say X and Y such that F(X,Y) is
 * maximum where F(X,Y) = sum of nodes in the path from root to X + sum of nodes
 * in the path from root to Y - sum of nodes in the common path from root to
 * first common ancestor of the Nodes X and Y. (G)
 * 
 */
public class FindMaxF {
	public int F(BinaryTree tree) {
		return F(tree.getRoot());
	}

	private int F(BinaryTreeNode node) {
		if (node == null)
			return Integer.MIN_VALUE;
		return node.value()
				+ Math.max(maxXY(node), Math.max(F(node.left()),
						F(node.right())));
	}

	private int maxXY(BinaryTreeNode node) {
		if (node == null || node.left() == null || node.right() == null)
			return Integer.MIN_VALUE;
		return maxValue(node.left()) + maxValue(node.right());
	}

	private int maxValue(BinaryTreeNode node) {
		return node == null? 0 : node.value() + Math.max(maxValue(node.left()), maxValue(node.right()));
	}

	/**************************************************************************
	 * F2: DP solution
	 **************************************************************************/

	public int F2(int[] a) {
		int N = a.length;
		int[] low = new int[N];
		int[] high = new int[N];
		int[] common = new int[N];

		for (int i = N - 1; i >= N / 2; i--) {
			high[i] = a[i];
			low[i] = Integer.MIN_VALUE;
		}

		for (int i = N / 2 - 1; i >= 0; i--) {
			int left = i * 2 + 1;
			int right = i * 2 + 2;
			int s = high[left]+common[left] > high[right]+common[right] ? left : right;
			int t = high[left]+common[left] > high[right]+common[right] ? right : left;

			if (low[s] > high[t] + common[t]) {
				low[i] = low[s];
				high[i] = high[s];
				common[i] = common[s] + a[i];
			} else {
				low[i] = high[t] + common[t];
				high[i] = high[s] + common[s];
				common[i] = a[i];
			}
		}

		return low[0] + high[0] + common[0];
	}

}
